﻿using System.Text;
/// <summary>
/// https://leetcode-cn.com/problems/permutation-sequence/
/// </summary>
public class Solution
{
    public string GetPermutation(int n, int k)
    {
        int[] factors = new int[] { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 };
        var digits = Enumerable.Range(1, 9).ToList();
        StringBuilder stringBuilder = new StringBuilder();
        k--;
        n--;
        for (; n >= 0; n--)
        {
            var f = factors[n];

            int index = k / f;
            _ = stringBuilder.Append(digits[index]);
            digits.RemoveAt(index);

            k %= f;
        }
        return stringBuilder.ToString();
    }
}


/* 下方案超时
/// <summary>
/// https://leetcode-cn.com/problems/permutation-sequence/
/// </summary>
public class Solution
{
    private IEnumerable<int> RemoveOne(IEnumerable<int> values, int value)
    {
        bool removed = false;
        foreach (var val in values)
        {
            if (val == value && !removed)
            {
                removed = true;
                continue;
            }
            yield return val;
        }
    }

    private IEnumerable<IEnumerable<int>> Permute(IEnumerable<int> nums, IEnumerable<int> cur)
    {
        if (!nums.Any())
            return new IEnumerable<int>[] { cur };

        var result = new List<IEnumerable<int>>();
        foreach (var num in nums)
            result.AddRange(Permute(RemoveOne(nums, num), cur.Concat(new int[] { num })));
        return result;
    }

    private IEnumerable<int> FromOneTo(int n)
    {
        for (int i = 0; i <= n; i++)
            yield return i;
    }

    public string GetPermutation(int n, int k)
    {
        var result = Permute(FromOneTo(n), Array.Empty<int>()).Skip(k - 1).First().Reverse();
        var intValue = 0;
        int power = 1;
        foreach(var r in result)
        {
            intValue += r * power;
            power *= 10;
        }
        return intValue.ToString();
    }
}
*/